package algorithm;

import java.awt.Point;

public class NlognWithIntegerArrayDistanceFinder extends AbstractDistanceFinder {

	public Point[] findMinimumDistance(Point[] points) {
		int[][] pts = convert(points);
		quicksort_x(pts);
		Point[] pr = new Point[2];
		int[][] pair = new int[2][2];
		findMinimumDistance(pts, 0, pts.length, pair);
		pr[0] = new Point(pair[0][0], pair[0][1]);
		pr[1] = new Point(pair[1][0], pair[1][1]);
		return pr;
	}

	private int[][] convert(Point[] pts) {
		int[][] ps = new int[pts.length][2];
		for (int i = 0; i < pts.length; i++) {
			ps[i][0] = pts[i].x;
			ps[i][1] = pts[i].y;
		}
		return ps;
	}

	private double findMinimumDistance(int[][] pts, int start, int end,
			int[][] pair) {
		double distance = 0;
		if (end - start <= 3) {
			return findMinDistance(pts, start, end, pair);
		}
		int middle = (start + end) / 2;
		int axisX = pts[middle][0];
		int[][] pair1 = new int[2][2];
		int[][] pair2 = new int[2][2];
		double d1 = findMinimumDistance(pts, start, middle, pair1);
		double d2 = findMinimumDistance(pts, middle, end, pair2);
		if (d1 <= d2) {
			distance = d1;
			pair[0][0] = pair1[0][0];
			pair[0][1] = pair1[0][1];
			pair[1][0] = pair1[1][0];
			pair[1][1] = pair1[1][1];
		} else {
			distance = d2;
			pair[0][0] = pair2[0][0];
			pair[0][1] = pair2[0][1];
			pair[1][0] = pair2[1][0];
			pair[1][1] = pair2[1][1];
		}
		// collect the points beside the line x = axisX
		// find the bounds.
		int p = middle, r = middle;
		while (p >= 0 && (axisX - pts[p][0]) <= distance)
			p--;
		p++;
		while (r < end && (pts[r][0] - axisX) <= distance)
			r++;
		// copy points into another array;
		int[][] tmppts = new int[r - p][2];
		for (int i = p; i < r; i++) {
			tmppts[i - p][0] = pts[i][0];
			tmppts[i - p][1] = pts[i][1];
		}
		// sort y
		quicksort_y(tmppts);

		// calc distances
		for (int i = 0; i < tmppts.length; i++) {
			for (int j = i + 1; j < i + 7 && j < tmppts.length; j++) {
				double d = calcDistance(tmppts[i], tmppts[j]);
				if (d < distance) {
					distance = d;
					pair[0] = tmppts[i];
					pair[1] = tmppts[j];
				}
			}
		}
		return distance;
	}

	private double findMinDistance(int[][] points, int start, int end,
			int[][] pair) {
		double distance = Double.MAX_VALUE;
		double tmpDistance = 0;
		for (int i = start; i < end - 1; i++) {
			for (int j = i + 1; j < end; j++) {

				tmpDistance = calcDistance(points[i], points[j]);
				if (tmpDistance < distance) {
					distance = tmpDistance;
					pair[0][0] = points[i][0];
					pair[0][1] = points[i][1];
					pair[1][0] = points[j][0];
					pair[1][1] = points[j][1];
				}
			}
		}
		return distance;
	}

	public void quicksort_x(int[][] pts) {
		quicksort_x(pts, 0, pts.length - 1);
	}

	private void quicksort_x(int[][] pts, int left, int right) {
		if (left >= right)
			return;
		int[] tmp = pts[right];
		int index;
		for (int i = index = left; i < right; ++i) {
			if (pts[i][0] <= tmp[0]) {
				swap(pts, index++, i);
			}
		}
		swap(pts, index, right);
		quicksort_x(pts, left, index - 1);
		quicksort_x(pts, index + 1, right);
	}

	public void quicksort_y(int[][] pts) {
		quicksort_y(pts, 0, pts.length - 1);
	}

	private void quicksort_y(int[][] pts, int left, int right) {
		if (left >= right)
			return;
		int[] tmp = pts[right];
		int indey;
		for (int i = indey = left; i < right; ++i) {
			if (pts[i][1] <= tmp[1]) {
				swap(pts, indey++, i);
			}
		}
		swap(pts, indey, right);
		quicksort_y(pts, left, indey - 1);
		quicksort_y(pts, indey + 1, right);
	}

	private void swap(int[][] pts, int i, int j) {
		int[] p = pts[i];
		pts[i] = pts[j];
		pts[j] = p;
	}

	private double calcDistance(int[] pt1, int[] pt2) {
		return Math.sqrt((pt1[0] - pt2[0]) * (pt1[0] - pt2[0])
				+ (pt1[1] - pt2[1]) * (pt1[1] - pt2[1]));
	}

}
